package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

//Java：滑动窗口最大值
public class SlidingWindowMaximum {
    public static void main(String[] args) {
        Solution solution = new SlidingWindowMaximum().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 1) {
                return nums;
            }
            int len = nums.length - k + 1;
            int[] res = new int[len];
            int num = 0;
            MyQueue myQueue = new MyQueue();
            for (int i = 0; i < k; i++) {
                myQueue.add(nums[i]);
            }
            res[num++] = myQueue.peek();
            for (int i = k; i < nums.length; i++) {
                myQueue.poll(nums[i - k]);
                myQueue.add(nums[i]);
                res[num++] = myQueue.peek();

            }
            return res;
        }
    }

    class MyQueue {
        Deque<Integer> queue = new LinkedList();

        void poll(int val) {
            if (!queue.isEmpty() && val == queue.peek()) {
                queue.poll();
            }
        }


        void add(int val) {
            while (!queue.isEmpty() && val > queue.getLast()) {
                queue.removeLast();
            }
            queue.add(val);
        }

        int peek() {
            return queue.peek();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}